#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// 二叉搜索（查找）树
// 左树上的所有节点均小于根节点的值，左树不为空
// 右树上的所有节点均大于根节点的值，右树不为空
//


// 二叉树每个节点不能多于有两个儿子
//
//

// 遍历方式
// 先序遍历: root节点  -> left子树 -> right子树
// 中序遍历: left子树  -> root节点 -> right子树
// 后序遍历: right子树 -> root节点 -> left子树
// 区别和联系；获取data的位置不同，区分是何种序的遍历？？有什么区别？

// 0 : pre
// 1 : mid
// 2 : post
//
//


static int traverse_sort_type = 0;

typedef struct b_tree{
	int data;
	struct b_tree *left;
	struct b_tree *right;
}b_tree,*b_node;


int traverse_tree(b_node root)
{
	if(!root)
		return 0;

	// 先序，pre
	if(traverse_sort_type == 0)
		printf("%d,",root->data);

	traverse_tree(root->left); // left 


	// 中序，mid
	if(traverse_sort_type == 1)
		printf("%d,",root->data);

	traverse_tree(root->right); // right

	// 后序，post
	if(traverse_sort_type == 2)
		printf("%d,",root->data);
	
	return 0;

}

int is_bst(b_node root)
{
	static b_node pre = NULL;

	if(root)
	{
		if(!is_bst(root->left))
			return 0;

		if(NULL != pre && root->data <= pre->data)
			return 0;

		pre = root;

		return is_bst(root->right);
	}

	// 空树 也被认为是二叉搜索（查找）树
	return 1;
}

int main()
{
	b_node node1 = (b_node)malloc(sizeof(b_tree)); 
	memset(node1,0,sizeof(b_tree));
	node1->data = 1;

	b_node node2 = (b_node)malloc(sizeof(b_tree)); 
	memset(node2,0,sizeof(b_tree));
	node2->data = 2;

	b_node node3 = (b_node)malloc(sizeof(b_tree)); 
	memset(node3,0,sizeof(b_tree));
	node3->data = 4;

	b_node node4 = (b_node)malloc(sizeof(b_tree)); 
	memset(node4,0,sizeof(b_tree));
	node4->data = 3;


	// init tree
	node1->left = node2;
	node1->right  = node3;
	node2->left = node4;


	// traverse tree
	traverse_sort_type = 0;
	traverse_tree(node1);
	printf("\n");

	traverse_sort_type = 1;
	traverse_tree(node1);
	printf("\n");
	
	traverse_sort_type = 2;
	traverse_tree(node1);
	printf("\n");

	// is_bst check
	printf("is bst %d\n",is_bst(node1));
	
	return 0;
}







